#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
// 102. 二叉树的层序遍历

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == nullptr)
            return res;

        queue<pair<TreeNode*, int>> q;    // 需要存储元素信息和层数信息。也可以设结构体表示。
        q.push(make_pair(root, 0)); // 将第0层的root放入队列中
        while(!q.empty()) {
            TreeNode* node = q.front().first;
            int level = q.front().second;   // 当前结点的层数
            q.pop();    // 队首的元素出队
            // 当前这个结点所在的层，是否是res已经包含的层
            if(level == res.size()) // 新结点在新的层中
                res.push_back(vector<int>());   // 创建一个新的vector
            // 可以放心的去放入结果向量中
            res[level].push_back(node->val);

            if(node->left)
                q.push(make_pair(node->left, level + 1 ));
            if(node->right)
                q.push(make_pair(node->right, level + 1));
        }

        return res;
    }
};
int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
